A War of Lions, Stags and Direwolves (formerly the King's Heir)
by Enchantress of Wolves
Summary: AU: Arya frees Ned from the dungeons before he's executed. On their way North, the pair finds Gendry and takes him in. Ned wants to raise an army against the Lannisters and recruit the Baratheons. Can they make it back home before it's too late and reunite with their family? And will Arya and Gendry's friendship ultimately turn into something more as the years go by? Rated T.
1. Escape from the Dungeons

Disclaimer: I don't own the A Song of Ice and Fire series nor do I own Game of Thrones. They belong to George R.R. Martin and David Benioff and D.B. Weiss respectively.

A/N: Thanks to everyone who reviewed, favorited and followed, it means a lot to me that so many of you enjoy this story. This is the re-vamped version.

* * *

Chapter 1 - Escape from the Dungeons

The sun was setting over King's Landing and the skies were a deep, dark orange with hardly a cloud in sight. While most of the city folk were now heading back to their homes, some were still out on the streets shopping or trading, or if they had no home to go to, simply lingering in the back alleys.

Among them, was eleven-year-old Arya Stark. She was currently chasing a skinny orange tabby cat through a narrow alleyway, with her long and tangled brown hair whipping behind her in the wind, and there was a determined expression on her dirt-covered face. She had been living in the streets for the past week, ever since her father (the hand of the king) had been arrested for treason and she had escaped the castle, and she had decided that she would stay here, hidden, for as long as possible. However, because of her highborn upbringing, she wasn't exactly used to being starving and not having a warm bed to sleep in, and she knew that it would be difficult for her if something didn't change soon.

Then suddenly, curse the old gods and the new, her stomach began to rumble and a feeling of hunger set in. Spotting a baker who was selling delicious smelling loaves of bread, she ran over to him. She knew that she wouldn't be able to afford it, but perhaps he would be kind enough to let her have some of his crusts.

"Excuse me, sir," she said in a humble voice, trying to appear innocent.

"What do you want, girl?" the baker spat back, glaring into her large, misty gray eyes.

"Do you think I could have some crusts?" Arya asked him as her stomach rumbled even louder. "I'm so hungry."

He shook his head. "Oh, piss off, girl. I don't do business with street urchins," he answered very unkindly and turned away, waving a large piece of bread in her direction as he went off chuckling.

Never in her life had Arya been denied food when she wanted it and the experience was quite disconcerting. In that moment, she wanted so badly to chase him down and tell him exactly who she was, but she instantly thought better of it and instead slumped away.

After all, she didn't want to be thrown back into the clutches of those evil, lying royals who were causing her family such harm and dishonor. Ever since she had met them, she had distrusted and disliked them, and now she wanted nothing more than to stick her sword right through the new king's head. Not only had he lied and cost her and her sister their direwolves, but he had been behind the death of her friend, the butcher's boy, and now he had locked up her kind, honorable father whom she loved more than anything in the world and was going to do the gods only knew what with him. It wasn't fair; they never should have come here, she thought.

Noticing an unoccupied area of ground, she slowly went over to sit down against the hard, stone wall and began drawing circles in the dust at her feet. _How had everything gone so horribly wrong?_ She wondered, holding back the tears that threatened to fall from her eyes as all of her thoughts and worries came rushing out at once, bombarding her.

 _What will become of Father? Of Sansa? Of me? Why couldn't we have stayed in Winterfell where we would've been safe and happy?_ Unable to hold back any longer, she began to cry softly into her hands. She was only a little girl, after all, and as much as she hated to admit it, she didn't really know how she was expected to survive in this cruel world full of liars and traitors without her father there to guide her. But that was when the harsh reality hit her, perhaps she _wasn't_ supposed to survive this. Perhaps she was simply to be collateral damage in something much bigger that she had no idea of yet. And that's when she heard the voices...

 _"Yeah, the Hand of the King..."_

 _"Exiled?"_

 _"...don't know yet, I think he'll likely be executed, but it's up to the king to decide..."_

Instantly, Arya scrambled back onto her feet and quickly wiped at the tears that were streaming down her face. She knew that she couldn't sit there and cry, not when her father was about to be condemned to such a horrible fate and she would lose him forever if she didn't act now. She knew that she had to do something - anything, to stop this, because by the gods, she was the only one who could. She was small and skilled with a sword and she knew that if anyone was going to rescue her father, it would have to be her, for they had no other allies here in King's Landing except for themselves. Besides, when it came to wielding a sword, her elder sister was about as useless as a loaf of bread and she was so tall that she would certainly be caught. Not to mention, she hadn't seen her sister in days, and she doubted that she would have the guts to sneak away and free their father when she was so busy swooning over the new king. _Idiot_.

Staring off towards the large castle in the distance, Arya noticed that as the skies changed into a deep, dark blue and the moon appeared in all its glory, the lights inside came on and emitted a bright, whitish glow. But if she looked down low enough, she could see the utter darkness that must have been the dungeons; where her beloved father sat in chains.

 _"It's got to be me. It's got to be me. It's got to be me,"_ She repeated the words over and over again in her head as she crept into the shadows and silently headed off towards the castle. Her head was spinning and she felt like if she stopped walking for a moment, she would either dart back in the other direction or fall over and get violently sick. She had only killed one stableboy before in her life and it had been a horrible accident, but now she knew that if she was to have any chance of saving her poor, innocent father's life, she would have to kill again and probably more than once. _I'm killing Gold Cloaks, they're as evil as the ones they work for, my father is innocent... I'll be doing good by killing them, won't I?_ In her eleven-year-old mind, that had to be a good enough rationalization.

xxx

The dungeons were dark, damp and cold with only the whitish-orange glow of the torches to provide even the slightest bit of warmth and light. Lord Eddard Stark couldn't remember a time when he had been so utterly miserable in his thirty-nine years of life and all he could think about were his poor, innocent daughters who were now entangled in this horrible ruin. And tears welled up in his smoky gray eyes.

Though he wouldn't admit it to himself quite yet, he was fairly certain that he was going to die. He was going to die even though he was innocent and simply trying to do right by the memory of his best friend, the deceased king. The thought sickened him to his core, but he knew that he would have to remain strong or the gods only knew what would become of his family, of his house. But one thing was for certain, he would rather die a horrible death than sacrifice his honor.

"Seven hells," he muttered under his breath, shaking his head and causing his long brown hair to fall into his face. He couldn't believe this was really happening; how could he have been so careless as to get himself caught conspiring against the royal family? How could he die and leave his daughters as lone wolves in the lion's den where they would certainly be torn to pieces? No, he couldn't let that happen...

Then suddenly, he heard a loud yelp and the clattering of metal on the hard stone ground, and then there were light, hurried footsteps headed his way. While he wasn't sure what this sudden commotion was, he knew that it couldn't be good. _Or could it?_ And then, right when he thought that his entire world was about to crumble around him, he saw the one person whom he hadn't been able to get off of his mind since his arrest; his youngest daughter. She was standing right in front of him with a bloody sword in her left hand and he realized, with horror, that it was in fact her own sword.

"Oh, Father!" she cried out, barreling into him.

"Arya!" Ned roared, only half angry as he held her against him as if his life depended on it. "What in the seven hells are you doing down here?"

"I'm sorry, Father, I'm so sorry," Arya sobbed, clinging to him desperately. "I ran away and I was hiding in the streets but tonight I heard some men saying that that horrid little king was either going to have you killed or exiled for treason, and I couldn't bear the thought of losing you, so I snuck back into the castle and I killed those guards out there with Needle - I crept up on one of them and drove my blade right through him and while the other one stood there looking for me I stabbed him too - they never even noticed me coming. I know I did a horrible thing, but you're innocent, you don't deserve what they want to do to you, so we have to run away - back to Winterfell, before they can take you away from me forever!"

As she rattled off her explanation, Ned could feel her warm tears soaking through his tunic and he gently peppered kisses on her forehead and in her hair. "Shush, it's alright, little love," he whispered soothingly as he continued to hold her in his strong arms. And in that moment, he knew that the gods had been merciful; they needed to escape. "We have to go, now, where's your sister?"

"I don't know," Arya admitted quietly, wiping her tears on her dirty sleeve. "I think she's still up in the castle, I haven't seen her in days."

Hearing this, Ned cursed under his breath as a harsh realization hit him. It would be far too risky to go up and retrieve his elder daughter, for if it was his head that they were after, they would certainly take it knowing that he tried to escape, and then he wouldn't be able to protect either one of his daughters. But if he escaped now, with only his younger daughter, then he could find a way to reunite his family again and protect them all.

"Right. I'm afraid we're going to have to leave her here then, only for now until we can get a safe distance away and I can have Robb bargain for her release," he decided, standing up and slinging his younger daughter over his shoulder. "He's called up the Northern banners in my defense so we need to get to him quickly and tell him what's happened. And we need to stay completely hidden on our way North, do you understand me? We'll have to set off before the sun rises and not rest until the sun sets, because that lying little king will send for us I swear to you. We need to get back home as quickly as possible so I need you to do exactly as I say, do you hear me?"

Arya nodded weakly. As much as she didn't always see eye to eye with her elder sister, the thought of leaving her in this horrible place bothered her immensely. "What if they hurt her?" she asked. "What if she thinks we've abandoned her?"

Ned sighed deeply as he crept towards the entrance. "They won't touch a hair on her head if they don't want the entire Northern army on their tails," he huffed in response. And he meant every word of it. If they harmed his daughter, his flesh and blood in any way, shape or form, there would be hell to pay. "And she may be hurt for a while when she realizes we've left, but she'll come to understand that I only left her so that I could protect _all_ of my children... that if I had rescued her, I would've been killed and there would've been no hope for any of us. You did a very brave thing, you did, letting me out like that. In a way, you saved all of us."

Creeping out into the warm night air, he settled a soft kiss on her forehead and Arya looked up at him. "Is there going to be a war?" she whispered, a fearful edge in her voice. "The North versus the South?"

"If that's the only thing that can end this reign of terror, then by the gods, yes," Ned replied with confidence. "Now we have to go, I'm sure the entire castle will be alerted of our escape soon enough and we want to get as far ahead of them as we can, so it will be impossible for them to catch us before we're behind Northern lines. Remember, to the Northerners, I am still their Warden, and they will stand behind me," he explained.

"Right," Arya said, a small smile spreading across her face. "Are you going to declare yourself King in the North?"

"I may have to," replied Ned, walking over to the stables and unchaining a nice brown horse. "Because I'm certainly not going to live in a kingdom ruled by - by that beast of a lad who knows nothing of what a good king should be."

He put Arya on first and then climbed up behind her. "Hup!" he shouted, slamming down the reins. "Go!"

"I'm scared, Father," Arya admitted as the horse took off into the darkness. "Would they execute an eleven-year-old girl for treason if they caught us?"

She had never been on the run before and she was horrified by the thought of being caught. But the wide smile on her father's face instantly settled her nerves; sometimes, he didn't even need to speak in order to reassure her.

"No, sweetling, I don't believe they would," Ned responded. "But your fate could be equally horrible, and that is why I am going to get us back home safely."

Hearing this, Arya simply nodded again. She had heard of the things that the kingdom did to little girls and she was in no hurry to experience any of that. "Right," was all she said.

As the night grew darker and they continued on their way out of the city and Northwards into the woods, Arya nuzzled into her father's chest. Though their circumstances were grim, she had faith in the old gods and the new that he would return her to Winterfell safely and they would reunite with their family. And she wasn't so scared anymore.

* * *

Note: Because I extended this chapter, the next chapter may be repetitive or not make sense, so I want to warn you to simply ignore the next two chapters until I can edit them tomorrow. Thanks!


	2. The Escape

A/N: Wow, I got LOTS of feedback on this. Unfortunately I can't see what any of the reviews said because for some reason they aren't showing up :/ but I wanted to say a huge thanks to everyone who responded to this story either by reviewing, following or favoriting! I'm still thinking I may fix it up but I'll likely leave it on here since ya'll have been so kind as to give me feedback! Thanks again!

* * *

Chapter 2 - The Escape

All that they could hear was the clacking of their horse's hooves against the hard ground as they rode out of King's Landing, and as soon as they entered the woods, the clacking became softer against the dirt.

Ned held his young daughter with one arm around her waist and the reins with his opposite hand as he continued to shout for the horse to go faster. He knew that if they didn't want the Gold Cloaks on their tails, they had better get out of there quickly.

"If they catch us, will they kill you?" Arya whispered into the darkness, burrowing herself deeper into her father's chest.

"Not if I can help it they won't," Ned responded gruffly, holding onto her tighter and settling a kiss on the top of her head. "There may be only one of me against an army of them, but my will to live is stronger than ever. I know things that could destroy them and that is why they wish to destroy me, but the North remembers, and if they harm or dishonor us again, they've got something else coming to them."

Arya creased an eyebrow and looked up at him curiously. "What do you know that they're so afraid of?"

Ned sighed heavily and bent his head low to her ear. "I don't think our new king deserves the throne. I think that because I'm fairly certain he isn't Robert's son, none of them are his children, they're full blooded Lannisters is what I've concluded." Perhaps he had said too much, but in a way, it was probably for the best if she knew.

"What?" Arya's mouth fell open. "How can they be full blooded Lannisters?"

"Shh." Ned's smoky gray eyes flashed warningly as he shushed her.

"Sorry," said Arya, realizing that she had been too loud.

Ned smiled softly and continued, "If I'm not mistaking, they are the queen's children with the kingslayer, her own twin brother. All of the Baratheons, even the bastards, have black hair and blue eyes no matter what their mother may look like. The royal children all have blonde hair and green eyes, the signature traits of Lannisters. The old hand of the king, Jon Arryn, I believe ended up figuring this out as well... and coincidentally, he too, ended up dead. This is why we need to get back to Winterfell and build up our army, we'll fight them with the entirety of the Northern forces and we will overthrow them," he explained quietly, a hint of determination in his voice. "And we will get your sister back and everything will be as it should be. I care about old Robert far too much to let his memory be betrayed in such a way, the throne rightfully belongs to the Baratheons, not the Lannisters, and I will take it upon myself to see that that happens."

"Whoa."

Arya couldn't believe what she was hearing, but at the same time, it explained everything. Suddenly, a rage like no other boiled up inside of her as she realized that the royals really were evil, traitorous liars who were trying to get rid of her father so that their secret wouldn't be exposed, and the remorse that she had been feeling after killing those Gold Cloaks and even the stableboy (who had threatened to turn her into them) suddenly vanished.

"I swear to you now, nothing else will happen to us. I know what I'm doing and I have vowed revenge for what that bitch - pardon my tongue - the queen did to Robert all these years, lying to him about those children that aren't even his... it's disgusting, it is," Ned muttered through clenched teeth as he smacked down on the horse's reins again.

"They were going to kill you or send you away, without even caring what happened to your family, all for the sake of their dirty little secret. If it were up to me, I'd have Joffrey's head on the tip of my sword so fast, and Cersei's too, they're evil! They lost me Nymeria and I'll probably never see her again because of them, I hate them, Father!" Arya said, starting to sniffle as more tears welled up in her eyes.

"Shush, sweetling, don't talk like that... we never know who could be lurking in these trees," whispered Ned, chancing a quick look around. "We can find Nymeria, we'll get her back, and everything will be alright again. I'm not going to let anything bad happen to us, I was vulnerable in those dungeons and only once did I think all hope was lost, but when you came to me I knew the gods had shown us mercy and never again will I succumb to such weakness. No matter what happens, death will not take me, because I need to be here to protect you, now don't I?"

At this, Arya nodded slowly. "So you promise me you won't die?" she sniffled, wiping her nose on her dirty sleeve.

"I promise." Ned knew that he couldn't predict the future, but he had a feeling that their odds were good if they could only get back to Winterfell. "And I promise that you won't either," he said with a smile, tickling her softly and causing her to let out an involuntary giggle.

They rode farther and farther into the trees until they were certain that they were far enough from King's Landing at this time of night that no one could find them. Then, and only then, did Ned stop the horse in the middle of a narrow clearing. He hopped off and then lifted Arya down as well, setting her back on her feet in the cool wet dirt.

"Come on, we'll make a fire," he said, grabbing an armful of wood that was lying nearby.

"Alright." Arya picked up two small sticks off the ground and started rubbing them together.

When they ignited, she threw them onto the wood pile and then curled herself up in her father's arms. After living alone on the streets for days, it was the best feeling in the world to be held by him again. She always felt so safe and happy, no matter the circumstances, when her father let her lay against his strong chest.

"Are you angry with me for killing those Gold Cloaks?" she asked after a few moments of silence.

Ned fixed her with a stern glare. "No, if you hadn't done it we wouldn't be here now, but don't make a habit of it. I don't want to see my sweet girl become a killer," he said, a smile tugging at the corners of his mouth. "And no word of it to your mother either."

Arya nodded, deciding not to tell him about the accident with the stableboy quite yet. "I understand."

"I'm glad," Ned chuckled softly into the warm night air. "Seven hells, I wonder what your mother will say when I only bring one daughter home with me..." He shook his head.

"At least you brought the one who doesn't whine and complain about everything," Arya said, earning a stern look from her father. "I'm only jesting," she added quickly.

Hearing a sudden crack from nearby, Ned turned his head sharply but when he saw no one, he focused his attention back on the small girl laying in his arms. "You really do look like your late Aunt Lyanna, you know... your long brown hair always tangled, an ever present spark in those beautiful gray eyes of yours..." he reminisced quietly, running his hands through her wild hair. "She too always preferred a sword or a crossbow over a needle and thread," he laughed.

"Would she have liked me?" Arya wanted to know.

"Aye, sweetling, she would've _loved_ you," Ned confirmed with a grin.

He tickled her again and she tried not to giggle, but it was no use. They rolled around near the fire for a few moments before Ned declared that it was Arya's bedtime, and put out the fire so they wouldn't attract attention to themselves. Then, he picked her up and carried her over to a patch of trees, where he lay down with her to go to sleep for the night.

"I love you, Father," Arya whispered against his soft leather tunic, before her eyelids fluttered shut.

"Aye, and I love you, sweet Arya," Ned murmured back, watching her small body move up and down with each breath as she fell into a deep slumber.

That night, Ned didn't sleep, as he knew that he would need to keep watch so that they could head out at the crack of dawn before the Gold Cloaks came for them, and he wanted to be awake and alert so that he could protect his most precious cargo; his sleeping daughter, should anyone come.

* * *

Whoa. I had MAJOR Ned and Arya feels while writing this XD I love their close father-daughter relationship. And I'm sorry to any Sansa fans who think I should've had them rescue her, I simply didn't see how that would work out without them getting caught but Ned won't forget her, he's going to cause some major havoc for the Lannisters not to worry! :P


	3. The Hostage of King's Landing

A/N: Right, so the review issue has clearly been resolved, and I was able to see what everyone said! So I'd like to give a huge shoutout to jean d'arc, Supremus85, purple sky always, NightSkyWolf, Master of Dragons God, KunnegAndris, Takai-taka, and Hunter1978 for their lovely reviews! To KunnegAndris on your suggestions - those were really good ideas about having Gendry help Arya break Ned out of the dungeons, so I might change the first chapter around when I edit this.I may have Gendry come with her but I was sort of thinking of them finding him injured after the attack on the Night's Watch recruits, so I also might simply add more detail on how exactly Arya pulled off her father's rescue to make it more believable. I'm going to post the third chapter now and then I'll likely get around to editing the beginning three chapters. I hope you all enjoy!

* * *

Chapter 3 - The Hostage of King's Landing

It was sunrise when thirteen-year-old Sansa Stark awoke to the entire castle in an uproar. She sat up in her bed and quickly ran a brush through her long red hair before hurrying out of her chambers to see what all of the commotion was.

"He escaped! The bloody hand escaped!" Several Gold Cloaks were shouting in the middle of the corridor.

"What's happened?" Sansa asked, worried.

But before her question could have been answered, she felt a rough hand on her shoulder and was spun around to face none other than her beloved, King Joffrey, and he looked angrier than ever.

"I'd hate to think you had anything to do with this!" he hissed, shaking her harshly and causing her to stumble backwards a bit.

"Do with what?" Sansa exclaimed, her sea blue eyes welling up with tears. She had no idea what in the seven hells was going on and she was really scared.

"Your father, he's escaped, and no one's seen your little cunt of a sister either!" Joffrey raged, slapping her hard across the face. "You helped them escape, didn't you? Didn't you?"

"What? No!" Sansa sobbed, turning away from him. "I swear I had nothing to do with it, I don't even know where they are!"

Joffrey didn't look convinced. "You wouldn't lie to me, would you?" he asked through gritted teeth. "Lying to a king is punishable by death, you know."

Sansa shook her head violently. "No! Your Grace, you must believe me! I don't know where my traitor father or sister have gone but I swear to you I'd tell you if I knew!"

Hearing this, the young king simply smirked. "Of course, milady," he said. His expression softened a bit. "You'll have breakfast with my mother and I while we send some men to look for them, now go dress in something pretty." Then he walked away from her and disappeared around a corner.

Now Sansa was left in the middle of the corridor with tears streaming down her pale cheeks. She didn't know where her father and sister were, but wherever they were, they had abandoned her and now she was stuck here as a hostage of the royal family. It wasn't fair. In that moment, she regretted every disagreement she had had with them and wondered if she had been left behind out of some fault of her own. After all, she _had_ been the one who had begged to stay behind...

 _Oh Father, Arya, where have you gone?_ She shook her head and wiped at her eyes before hurrying back into her chambers. She put on a rose colored dress and went to join the King and Queen Regent for breakfast, praying to the old gods and the new that her father and sister could escape the Gold Cloaks when they went looking for them.

xxx

Arya woke up to the sun in her face and when she blinked a few times, she could see the kind gray eyes of her father staring down at her. He was slowly untangling her long hair with his fingers and seeing that she was awake, he planted a kiss on her forehead.

"Good morning, little love," Ned whispered as some birds chirped up in the trees around them.

"I'm not little!" exclaimed Arya indignantly, smiling at the sight of the beautiful sunrise.

Ned laughed. "Of course you're not," he said, tickling his young daughter under her arms. "Come on, we're going home to Winterfell - to your mother, to Robb, to Bran and Rickon. If we hurry we should be there in the next day or two."

"Alright," Arya agreed, nodding. "Do you think Sansa knows we're gone yet?" she asked after a few moments of silence, a worried expression on her face.

"Aye, I'd imagine so. I'm sure the entire bloody castle knows and they've sent out their damn Gold Cloaks already," Ned answered grimly. "Which is why we need to get going, come on."

He hoisted her up onto their horse again and untied it from a nearby tree before hopping up himself. "Hup! Go!" he yelled, slamming down the reins as it took off through the trees again.

Hanging onto her father for dear life, Arya asked, "What will happen when we get back to Winterfell?"

"We're going to rally the Northern houses and do everything we can to get your sister back, and to get that incest child off the throne for good," Ned answered roughly. "It's going to be a war of wolves and lions, and it's not going to be pretty, but winter is coming... and those Southerners won't know what hit them, but we'll be ready for it."

"They should've known not to mess with the Starks," Arya said, a smile tugging at the corners of her mouth. "Because direwolves are vicious, and we're going to rip their precious golden manes off in one bite!"

Hearing this, Ned couldn't help but chuckle, and he nodded. "You're right, sweetling, those Lannisters have another thing coming to them."

* * *

Again, definitely going to clean this up after this chapter, I won't post any more chapters until I've edited these three but I wanted to put this up to give you all a sense of where this is going and to let you see Sansa.

Thanks for reading!


End file.
